package com.bang.study.day08;

/**
 * @Auther: Bang
 * @Date: 2019/9/19 0019 09:43
 * @Description: 红黑树
 */
public class RBTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;

    private static final boolean BLACK = false;

    private class Node {
        public K key;
        public V value;
        public boolean color;
        public Node left;
        public Node right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.color = RED;
        }
    }

    private Node root;

    private int size;

    public RBTree() {
        this.root = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 左旋转
     * <p>
     * node                     x
     * /   \     左旋转         /  \
     * T1   x   --------->   node   T3
     * / \              /   \
     * T2 T3            T1   T2
     *
     * @param node
     * @return
     */
    private Node leftRotate(Node node) {
        Node x = node.right;

        // 左旋转
        node.right = x.left;
        x.left = node;

        // 维护颜色  x颜色等于node的颜色 node的颜色变为Red
        x.color = node.color;
        node.color = RED;

        return x;
    }


    /**
     * 右旋转
     *       node                   x
     *      /   \     右旋转       /  \
     *     x    T2   ------->   y   node
     *    / \                       /  \
     *   y  T1                     T1  T2
     *
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {
        Node x = node.left;

        // 右旋转
        node.left = x.right;
        x.right = node;

        // 维护颜色  x颜色等于node的颜色 node的颜色变为Red
        x.color = node.color;
        node.color = RED;

        return x;
    }


    /**
     * 颜色翻转 根节点红色 子节点黑色
     *
     * @param node
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    // 返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node node, K key) {

        if (node == null)
            return null;

        if (key.equals(node.key))
            return node;
        else if (key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else // if(key.compareTo(node.key) > 0)
            return getNode(node.right, key);
    }

    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if (node == null)
            throw new IllegalArgumentException(key + " doesn't exist!");
        node.value = newValue;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }


    // 判断节点node的颜色
    private boolean isRed(Node node){
        if(node == null)
            return BLACK;
        return node.color;
    }

    /**
     * 向红黑树中添加新的元素(key, value)
     *
     * @param key
     * @param value
     */
    public void add(K key, V value) {
        root = add(root, key, value);
        root.color = BLACK;
    }

    /**
     * 添加元素,返回根节点
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            // 默认添加的节点为红色
            return new Node(key, value);
        } else {
            if (key.compareTo(node.key) > 0) {
                node.right = add(node.right, key, value);
            } else if (key.compareTo(node.key) < 0) {
                node.left = add(node.left, key, value);
            } else {
//                key.compareTo(node.key) ==0
                node.value = value;
            }

            // 维持平衡的时机 在元素添加完后回溯上级

            if (isRed(node.right) && !isRed(node.left)) {
                node = leftRotate(node);
            }

            if (isRed(node.left) && isRed(node.left.left)) {
                node = rightRotate(node);
            }

            if (isRed(node.left) && isRed(node.right)) {
                flipColors(node);
            }
            return node;
        }

    }


    public V remove(K key){
        V v = get(key);
        if (v!=null) {
           root=remove(root, key);
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node==null) {
            return null;
        }else {
            if (node.left==null) {

            } else if (node.right == null) {

            }else{

            }
        }
        return null;
    }


}
